#include <stdio.h>
#include "algo_quickSort.h"
#include "algo_findKsmallest.h"

#define numElement 20

int findKsmallest(int a[], int length, int k) {
	int startIndex = 0;
	int endIndex = length - 1;
	int partitionIndex;
	do {
		partitionIndex = (startIndex + endIndex) / 2;
		partitionIndex = partition(a, startIndex, endIndex, partitionIndex); 
		if (partitionIndex < k) {
			startIndex = partitionIndex + 1;
		    endIndex = length - 1;
		}
		else {
			startIndex = 0;
			endIndex = partitionIndex - 1;
		}
	} while (partitionIndex != k);

	return a[partitionIndex];
}

void test_algo_findKsmallest() {
	int data[numElement] = { 12, 1, 3, 9, 9, 8, 2, 7, 10, 15, 4, 6, 11, 20, 30, 14, 17, 25, 29, 26 };

	printf("Input array.\n");
	for (int i = 0; i < numElement; i++) {
		printf("%d", data[i]);
		if ( i < numElement - 1 )
			printf(", ");
		else
			printf("\n");
	}
	printf("\n");

	int k = 17;
	int result = findKsmallest(data, numElement, k);
	printf("The %d-th smallest element is %d.\n\n", k, result);
}
